In this paper, we put forward a new method to construct n-variable Boolean functions with optimal algebraic immunity based on the factorization of n. Computer investigations for small values of n indicate that a class of Boolean functions constructed by the new method has a very good nonlinearity and also a good behavior against fast algebraic attacks.

Because of the algebraic attacks, a high algebraic immunity is now an important criteria for Boolean functions used in stream ciphers. In 2011, X.Y. Zeng et al. proposed three constructions of balanced Boolean functions with maximum algebraic immunity, the constructions are based on univariate polynomial representation of Boolean functions. In this paper, we will improve X.Y. Zeng et al.' constructions to obtain more even-variable Boolean functions with maximum algebraic immunity. It is checked that, our new functions can have as high nonlinearity as X.Y. Zeng et al.' functions.

Multicarrier communications including orthogonal frequency-division multiplexing (OFDM) is a technique which has been adopted for various wireless applications. However, a major drawback to the widespread acceptance of OFDM is the high peak-to-mean envelope power ratio (PMEPR) of uncoded OFDM signals. Finding methods for construction of sequences with low PMEPR is an active research area. In this paper, by employing some new shortened and extended Golay complementary pairs as the seeds, we enlarge the family size of near-complementary sequences given by Yu and Gong. We also show that the new set of sequences we obtained is just a reversal of the original set. Numerical results show that the enlarged family size is almost twice of the original one. Besides, the Hamming distances of the binary near-complementary sequences are also analyzed.

Constructing APN or 4-differentially uniform permutations achieving all the necessary criteria is an open problem, and the research on it progresses slowly. In ACISP 2011, Carlet put forth an idea for constructing differentially uniform permutations using extension fields, which was illustrated with a construction of a 4-differentially uniform (n,n)-permutation. The permutation has optimum algebraic degree and very good nonlinearity. However, it was proved to be a permutation only for n odd. In this note, we investigate further the construction of differentially uniform permutations using extension fields, and construct a 4-differentially uniform (n,n)-permutation for any n. These permutations also have optimum algebraic degree and very good nonlinearity. Moreover, we consider a more general type of construction, and illustrate it with an example of a 4-differentially uniform (n,n)-permutation with good cryptographic properties.

In this comment, an inequality of algebraic immunity of the sum of two Boolean functions is pointed out to be generally incorrect. Then we present some results on how to impose conditions such that the inequality is true. Finally, complete proofs of two existing results are given.

It is well known that Boolean functions used in stream and block ciphers should have high algebraic immunity to resist algebraic attacks. Up to now, there have been many constructions of Boolean functions achieving the maximum algebraic immunity. In this paper, we present several constructions of rotation symmetric Boolean functions with maximum algebraic immunity on an odd number of variables which are not symmetric, via a study of invertible cyclic matrices over the binary field. In particular, we generalize the existing results and introduce a new method to construct all the rotation symmetric Boolean functions that differ from the majority function on two orbits. Moreover, we prove that their nonlinearities are upper bounded by .

Based on Tu-Deng's conjecture and the Tu-Deng function, in 2010, X. Tang et al. proposed a class of Boolean functions in even variables with optimal algebraic degree, very high nonlinearity and optimal algebraic immunity. In this corresponding, we consider the concatenation of Tang's function and another Boolean function, and study its cryptographic properties. With this idea, we propose a class of 1-resilient Boolean functions in odd variables with optimal algebraic degree, good nonlinearity and suboptimal algebraic immunity based on Tu-Deng's conjecture.

In this note, we go further on the “basis exchange” idea presented in [2] by using Mobious inversion. We show that the matrix S1(f)S0(f)-1 has a nice form when f is chosen to be the majority function, where S1(f) is the matrix with row vectors υk(α) for all α ∈ 1f and S0(f)=S1(f ⊕ 1). And an exact counting for Boolean functions with maximum algebraic immunity by exchanging one point in on-set with one point in off-set of the majority function is given. Furthermore, we present a necessary condition according to weight distribution for Boolean functions to achieve algebraic immunity not less than a given number.

A Boolean function is said to be correlation immune if its output leaks no information about its input values. Such functions have many applications in computer security practices including the construction of key stream generators from a set of shift registers. Finding methods for easy construction of correlation immune Boolean functions has been an active research area since the introduction of the notion by Siegenthaler. In this paper, we present several constructions of nonpalindromic correlation immune symmetric Boolean functions. Our methods involve finding binomial coefficient identities and obtaining new correlation immune functions from known correlation immune functions. We also consider the construction of higher order correlation immunity symmetric functions and propose a class of third order correlation immune symmetric functions on n variables, where n+1(≥ 9) is a perfect square.

In this paper, we deal with the algebraic immunity of the symmetric Boolean functions. The algebraic immunity is a property which measures the resistance against the algebraic attacks on symmetric ciphers. It is well known that the algebraic immunity of the symmetric Boolean functions is completely determined by a narrow class of annihilators with low degree which is denoted by G(n,). We study and determine the weight support of part of these functions. Basing on this, we obtain some relations between the algebraic immunity of a symmetric Boolean function and its simplified value vector. For applications, we put forward an upper bound on the number of the symmetric Boolean functions with algebraic immunity at least d and prove that the algebraic immunity of the symmetric palindromic functions is not high.

A class of balanced semi-bent functions with an even number of variables is proposed. It is shown that they include one subclass of semi-bent functions with maximum algebraic degrees. Furthermore, an example of semi-bent functions in a small field is given by using the zeros of some Kloosterman sums. Based on the result given by S.Kim et al., an example of infinite families of semi-bent functions is also obtained.

Constructing degree-optimized resilient Boolean functions with high nonlinearity is a significant study area in Boolean functions. In this letter, we provide a construction of degree-optimized n-variable (n odd and n ≥ 35) resilient Boolean functions, and it is shown that the resultant functions achieve the currently best known nonlinearity.

In this paper, we explicitly construct a large class of symmetric Boolean functions on 2k variables with algebraic immunity not less than d, where integer k is given arbitrarily and d is a given suffix of k in binary representation. If let d = k, our constructed functions achieve the maximum algebraic immunity. Remarkably, 2⌊ log2k ⌋ + 2 symmetric Boolean functions on 2k variables with maximum algebraic immunity are constructed, which are much more than the previous constructions. Based on our construction, a lower bound of symmetric Boolean functions with algebraic immunity not less than d is derived, which is 2⌊ log2d ⌋ + 2(k-d+1). As far as we know, this is the first lower bound of this kind.

In this paper, we constructed six infinite classes of balanced Boolean functions. These six classes of Boolean functions achieved optimal algebraic degree, optimal algebraic immunity and high nonlinearity. Furthermore, we gave the proof of the lower bound of the nonlinearities of these balanced Boolean functions and proved the better lower bound of nonlinearity for Carlet-Feng's Boolean function.

A method to construct Boolean functions with maximum algebraic immunity have been proposed in . Based on that method, we propose a different method to construct Boolean functions on even variables with maximum algebraic immunity in this letter. By counting on our construction, a lower bound of the number of such Boolean functions is derived, which is the best among all the existing lower bounds.

It is known that Boolean functions used in stream ciphers should have good cryptographic properties to resist fast algebraic attacks. In this paper, we study a new class of Boolean functions with good cryptographic properties: balancedness, optimum algebraic degree, optimum algebraic immunity and a high nonlinearity.

Decision diagrams (DDs) are data structures commonly used for representation of discrete functions with large number of variables. Binary DDs (BDDs) are used for representation and manipulation with Boolean functions. Complexity of a BDD is usually measured by its size, that is defined as the number of non-terminal nodes in the BDD. Minimization of the sizes of DDs is a problem greatly considered in literature and many related algorithms (exact and heuristic) have been proposed. However, there are many functions for which BDDs when minimized are still large and can have even an exponential size in the number of variables. An approach to derive compact decision diagram representations for such functions is transformation of BDDs into Multi-valued DDs (MDDs) and Heterogeneous MDDs (HMDDs). Complexity of MDDs and HMDDs is measured by the cost which is a generalization of the notion of the size by taking into account complexity of nodes in MDDs and HMDDs. This paper presents a method for transformation of BDD into HMDD with minimal cost. The proposed method reduces the time for determination of the type of nodes in HMDDs by introducing a matrix expressing dependency (interconnections) among nodes at different levels. Comparing to other methods for conversion of BDDs into HMDDs, the method reduces the number of traverses of a BDD necessary for collecting enough information to construct an equivalent HMDD. For an experimental verification of its efficiency, the method is applied to construction of HMDDs for some benchmark functions and their arithmetic and Walsh spectra.

A function F:F2n F2n is almost perfect nonlinear (APN) if, for every a 0, b in F2n, the equation F(x)+F(x+a)=b has at most two solutions in F2n. When used as an S-box in a block cipher, it contributes optimally to the resistance to differential cryptanalysis. The function F is almost bent (AB) if the minimum Hamming distance between all its component functions v F, v∈F2n {0} (where "" denotes any inner product in F2n ) and all affine Boolean functions on F2n takes the maximal value 2n-1-2. AB functions exist for n odd only and contribute optimally to the resistance to the linear cryptanalysis. Every AB function is APN, and in the n odd case, any quadratic APN function is AB. The APN and AB properties are preserved by affine equivalence: F F' if F'=A1 F A2, where A1,A2 are affine permutations. More generally, they are preserved by CCZ-equivalence, that is, affine equivalence of the graphs of F: {(x,F(xv)) | x∈ F2n} and of F'. Until recently, the only known constructions of APN and AB functions were CCZ-equivalent to power functions F(x)=xd over finite fields (F2n being identified with F2n and an inner product being x y=tr(xy) where tr is the trace function). Several recent infinite classes of APN functions have been proved CCZ-inequivalent to power functions. In this paper, we describe the state of the art in the domain and we also present original results. We indicate what are the most important open problems and make some new observations about them. Many results presented are from joint works with Lilya Budaghyan, Gregor Leander and Alexander Pott.

A tree-shellable function is a positive Boolean function which can be represented by a binary decision tree whose number of paths from the root to a leaf labeled 1 equals the number of prime implicants. In this paper, we consider the tree-shellability of DNFs with restrictions. We show that, for read-k DNFs, the number of terms in a tree-shellable function is at most k2. We also show that, for k-DNFs, recognition of ordered tree-shellable functions is NP-complete for k=4 and tree-shellable functions can be recognized in polynomial time for constant k.

In the past twenty years, there were only a few constructions for Boolean functions with nonlinearity exceeding the quadratic bound 2n-1-2(n-1)/2 when n is odd (we shall call them Boolean functions with very high nonlinearity). The first basic construction was by Patterson and Wiedemann in 1983, which produced unbalanced function with very high nonlinearity. But for cryptographic applications, we need balanced Boolean functions. Therefore in 1993, Seberry, Zhang and Zheng proposed a secondary construction for balanced functions with very high nonlinearity by taking the direct sum of a modified bent function with the Patterson-Wiedemann function. Later in 2000, Sarkar and Maitra constructed such functions by taking the direct sum of a bent function with a modified Patterson-Wiedemann function. In this paper, we propose a new secondary construction for balanced Boolean functions with very high nonlinearity by recursively composing balanced functions with very high nonlinearity with quadratic functions. This is the first construction for balanced function with very high nonlinearity not based on the direct sum approach. Our construction also have other desirable properties like high algebraic degree and large linear span.